Back in the 1990s we started work on pedagogical agents, a new user interface paradigm for interactive learning environments. Pedagogical agents are autonomous characters that inhabit learning environments and can engage with learners in rich, face-to-face interactions. Building on this work, in 2000 we, together with our colleague, Jeff Rickel, published an article on pedagogical agents that surveyed this new paradigm and discussed its potential. We made the case that pedagogical agents that interact with learners in natural, life-like ways can help learning environments achieve improved learning outcomes. This article has been widely cited, and was a winner of the 2017 IFAAMAS Award for Influential Papers in Autonomous Agents and Multiagent Systems (IFAAMAS, 2017).